package week06

import "math"

// 309. 最佳买卖股票时机含冷冻期
// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

func maxProfit(prices []int) int {
	var dp = make([][][]int, len(prices)+1)
	for i := range dp {
		dp[i] = make([][]int, 2)
		for j := range dp[i] {
			dp[i][j] = []int{math.MinInt32, math.MinInt32}
		}
	}
	dp[0][0][0] = 0
	for i := 1; i <= len(prices); i++ {
		for j := 0; j <= 1; j++ {
			for k := 0; k <= 1; k++ {
				dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][k])
				if j == 0 && k == 0 {
					dp[i][0][1] = max(dp[i][0][1], dp[i-1][1][k] + prices[i-1])
				} else if k == 0 {
					dp[i][1][k] = max(dp[i][1][k], dp[i-1][0][k] - prices[i-1])
				}

			}
		}
	}
	var ans = 0
	for k := 0; k <= 1; k++ {
		ans = max(ans, dp[len(prices)][0][k])
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}